package main

import "fmt"

type Node struct {
	value       string // 值
	left, right *Node
}

func (node *Node) print() {
	fmt.Print(node.value, " ")
}

func (node *Node) setValue(val string) {
	if node == nil {
		fmt.Print("值为nil的节点将被忽略")
		return
	}
	node.value = val
}

func (node *Node) preOrder() {
	if node == nil {
		return
	}
	node.print()
	node.left.preOrder()
	node.right.preOrder()
}

func (node *Node) middleOrder() {
	if node == nil {
		return
	}
	node.left.middleOrder()
	node.print()
	node.right.middleOrder()
}

func (node *Node) postOrder() {
	if node == nil {
		return
	}
	node.left.postOrder()
	node.right.postOrder()
	node.print()
}

func (node *Node) breadthFirstSearch() {
	if node == nil {
		return
	}
	result := []string{}
	nodes := []*Node{node}
	for len(nodes) > 0 {
		curNode := nodes[0]
		nodes = nodes[1:]
		result = append(result, curNode.value)
		if curNode.left != nil {
			nodes = append(nodes, curNode.left)
		}
		if curNode.right != nil {
			nodes = append(nodes, curNode.right)
		}
	}
	for _, v := range result {
		fmt.Print(v, " ")
	}
}

func createNode(v string) *Node {
	return &Node{value: v}
}

func main() {
	root := createNode("1")
	root.left = createNode("2")
	root.left.left = createNode("4")
	root.left.right = createNode("5")
	root.left.right.left = createNode("7")
	root.left.right.left.right = createNode("8")
	root.right = createNode("3")
	root.right.right = createNode("6")

	fmt.Println("前序遍历:")
	root.preOrder()

	fmt.Println("\n中序遍历:")
	root.middleOrder()

	fmt.Println("\n后序遍历:")
	root.postOrder()

	fmt.Println("\n顺序遍历:")
	root.breadthFirstSearch()
}
